package week_10;

public class NumArrayBinaryIndexedTree {
    int[] c;
    int[] a;
    int n;

    public NumArrayBinaryIndexedTree(int[] nums) {
        // 树状数组的初始化
        this.n = nums.length;
        this.a = new int[n + 1];
        this.c = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = nums[i - 1];
            add(i, a[i]);
        }
    }

    public void update(int index, int val) {
        index += 1;
        int diff = val - a[index];
        a[index] = val;
        add(index, diff);
    }

    public int sumRange(int left, int right) {
        left += 1;
        right += 1;
        return query(right) - query(left - 1);
    }

    public void add(int x, int delta) {
        for (; x <= n; x += lowbit(x)) c[x] += delta;
    }

    public int query(int x) {
        int ans = 0;
        for (; x > 0; x -=lowbit(x)) ans += c[x];
        return ans;
    }

    public int lowbit(int x) {
        return x & -x;
    }

    public static void main(String[] args) {
//["NumArray","update","update","update","sumRange","update","sumRange","update","sumRange","sumRange","update"]
//[update[[7,2,7,2,0]],[4,6],[0,2],[0,9],[4,4],[3,8],[0,4],[4,1],[0,3],[0,4],[0,4]]
        int[] nums = {7, 2, 7, 2, 0};
        NumArrayBinaryIndexedTree numArray = new NumArrayBinaryIndexedTree(nums);
        numArray.update(4, 6);
        numArray.update(0, 2);
        numArray.update(0, 9);

        numArray.update(1, 2);
        int ans2 = numArray.sumRange(0, 2);
        System.out.println(ans2);
    }
}
